LANs to enable communication between various types of computing devices are well known in the art. Each of the various computing devices is connected to the LAN via a bus interface unit (BIU). LANs utilize protocols of various types, also well known in the art, to allow communication over the network to be conducted in an expedient and efficient manner. In particular, it is a desirable feature of such protocols to minimize the delay incurred by a BIU in waiting for access to the transmission medium in order to transmit an information packet from its associated computing device. It is also a desirable feature to maximize the effective data rate of the medium, i.e. the number of information packets successfully transmitted on the medium per unit time.
A contention bus accessing protocol, well known in the art, is one in which, generally, each BIU gains access to the transmission medium to transmit its information packet(s) at any time the subject BIU determines the transmission medium is idle. When more than one BIU attempts to gain access to the transmission medium simultaneously, a collision occurs and each BIU generally discontinues its transmission for a randomly selected time interval, thereafter reattempting to gain access to the medium. Examples of such a control structure are found in LANs following IEEE 802.3 and the Ethernet (a trademark of Xerox Corporation) specifications for a carrier-sense multiple-access (CSMA/CD) protocol. Such protocols generally incur unacceptable delays at times when many BIUs have information packets to transmit and therefore may collisions occur. Further, the loss of all information packets involved in each collision has an adverse impact on the effective transmission medium data rate. Additionally, since access to the medium after each collision is determined by a random time factor, it is impossible to establish an upper bound on the maximum time interval between times when a BIU gains access to the transmission medium.
The preemptive BID Communication System, disclosed in U.S. Pat. No. 4,517,670, which is incorporated in its entirety herein by reference, provides an improved contention protocol wherein, of the the BIUs involved in a collision, one is enabled to continue information packet transmission. The other BIUs involved in the collision are designated preempted BIUs and are allowed to transmit following the collision. In accordance with that protocol, a series of communication periods are provided for the preempted BIUs after the collision. During each communication period, the preempted BIUs follow a method which allows them to determine, in accordance with their respective physical locations along the network transmission medium, which one of them can transmit its information packet(s). After each preempted BIU successfully completes its transmission, another communication period is commenced, this repetitive cycle being continued until all preempted BIUs successfully transmit their respective information packets. Following transmission by the last preempted BIU and before BIUs again contend for bus access, the BIUs must wait for one additional communication period. Further in accordance with the Preemptive BID protocol, even when there are no preempted BIUs, a communication period follows each successful packet transmission. Additionally, each BIU independently enters a captive mode, upon successfully transmitting its information packet, during which it refrains from attempting to gain bus access. Each captive mode BIU cannot leave that mode until it successfully measures a captive period during which the system transmit and receive buses are silent. The captive and communication periods are each typically chosen equal to the two-way propagation delay in the network transmission medium.
In order to enable continued transmission by one BIU involved in a collision, the Preemptive BID protocol additionally requires each information packet to carry an excessively long preamble portion, e.g. a preamble having a transmission time on the order of the network medium two-way propagation delay. Thus, the Preemptive BID protocol provides improvements, over the CSMA/CD protocol described above, by preserving one information packet in a collision and affording BIUs with the preempted status an immediate opportunity to transmit their respective packets. However, it also carries a substantial overhead, to wit, the long communication and captive periods and long information packet preamble both of which serve to degrade the effective transmission medium data rate. Further, the Preemptive BID system is a complex protocol and is therefore difficult to implement.
It is therefore an object of the present invention to provide a protocol, for transmitting information packets in a LAN, which is relatively easy to implement, which maximizes transmission medium effective data rate and for which can be determined a maximum limit on the interval between times when a BIU can gain access to the medium.